package com.waiting.leetcode;

/**
 * @Description
 * @Author bjweitingting
 * @Date 2019/3/13
 **/
public class FlattenBinaryTreeToLinkedList114 {

    public void flatten(TreeNode root) {
        rightNode(root);
    }

    public TreeNode rightNode(TreeNode root) {
        if (root == null) {
            return null;
        }
        //当前节点是叶子节点
        if (root.left == null && root.right == null) {
            return root;
        }
        TreeNode rightNode = null;
        rightNode = rightNode(root.left);
        if (rightNode != null) {
            rightNode.right = root.right;
            root.right = root.left;
            root.left = null;
            //采用中序遍历法
            //如果root节点有右子树
            //则从右子树中找最后一个节点
            //如果没有右子树，则左子树的最后一个节点就是root的最后一个节点
            if (rightNode.right != null) {
                return rightNode(rightNode.right);
            } else {
                return rightNode;
            }
        } else {
            return rightNode(root.right);
        }
    }
}
